class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.data_key = []
        self.data = {}

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.data:
            self.data_key.remove(key)
            self.data_key.insert(0, key)
            return self.data[key]
        else:
            return -1        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.data_key:
            self.data_key.remove(key)
        self.data[key] = value
        self.data_key.insert(0, key)
        if len(self.data_key) > self.capacity:
            remove_key = self.data_key[self.capacity]
            del self.data[remove_key]
            self.data_key = self.data_key[: self.capacity]

if __name__ == '__main__':
    cache = LRUCache(2)

    cache.put(1, 1)
    cache.put(2, 2)
    print cache.get(1)
    cache.put(3, 3)
    print cache.get(2)
    cache.put(4, 4)
    print cache.get(1)
    print cache.get(3)
    print cache.get(4)